var letterCombinations = function (digits) {
  const len = digits.length;
  if (!len) return [];
  const combinations = [];

  const map = new Map([
    ["2", "abc"],
    ["3", "def"],
    ["4", "ghi"],
    ["5", "jkl"],
    ["6", "mno"],
    ["7", "pqrs"],
    ["8", "tuv"],
    ["9", "wxyz"],
  ]);
  // 维护一个公共的字符串或数组，通过回溯算法不断的累加
  backtracking(0, "");

  function backtracking(idx, combination) {
    if (idx === len) {
      combinations.push(combination);
    } else {
      const digit = digits[idx];
      const backStr = map.get(digit);
      for (let i = 0; i < backStr.length; i++) {
        combination += backStr[i];
        backtracking(idx + 1, combination);
        combination = combination.slice(0, idx);
      }
    }
  }

  return combinations;
};

console.log(letterCombinations("23"));
